// 节点对象类型
type GridNode = cc.Node & {
    // 网格坐标 GridPos
    gridPos: GridPos
    // 是否可通过
    moveAbled: boolean
    // 是否舍弃路径点
    isClose: boolean
    // 是否可选路径点
    isOpen: boolean
    // 已连接的上一个路径点
    last: GridNode
    // 已连接的下一个路径点
    next: GridNode
    // 抵达当前路径点的步数
    curStepNum: number
    expectStepNum: number
    sumNum: number
}

// 网格坐标类型
type GridPos = {
    // 横坐标
    x: number
    // 纵坐标
    y: number
}

/**
 * A*寻路工具
 */
export class AStar {

    private _widthNum: number
    private _heightNum: number
    private _gridMap: Map<number, Map<number, GridNode>>
    private _closeItems: Map<number, GridNode>
    private _openGridNodes: GridNode[]
    private _steps: GridNode[]
    private _isSmart: boolean
    private _resultCall: (steps: GridNode[]) => void
    private _startGridNode: GridNode
    private _endGridNode: GridNode

    /**
     * 根据指定网格信息，初始化工具
     * @param gridMap 网格对象(网格必须是四边形矩形网格)
     */
    constructor(gridMap: Map<number, Map<number, GridNode>>) {
        cc.log(`${cc.js.getClassName(this)} constructor gridMap = `, gridMap)

        this._widthNum = gridMap.size
        this._heightNum = gridMap.get(0).size
        this._gridMap = gridMap
    }

    //==============================================================================================================================
    //========================================================= 内部方法 ============================================================
    //==============================================================================================================================

    /**
     * 根据指定起点和终点寻路
     * @param startGridNode 起点
     * @param endGridNode 终点
     */
    _startSearch(startGridNode: GridNode, endGridNode: GridNode): void {
        // cc.log(`${cc.js.getClassName(this)} _startSearch`)

        this._getClosestOpenGridNodes(startGridNode, startGridNode, endGridNode)
    }

    /**
     * 根据起点和终点以及当前位置，搜索路径
     * @param curGridNode 当店节点
     * @param startGridNode 起点
     * @param endGridNode 终点
     * @returns 是否已经搜索完所有可选节点
     */
    _getClosestOpenGridNodes(curGridNode: GridNode, startGridNode: GridNode, endGridNode: GridNode): boolean {
        // cc.log(`${cc.js.getClassName(this)} _getClosestOpenGridNodes`)

        curGridNode.isClose = true
        this._closeItems.set(this._closeItems.size, curGridNode)

        let gridPoss = [
            cc.v2(curGridNode.gridPos.x + 1, curGridNode.gridPos.y),
            cc.v2(curGridNode.gridPos.x, curGridNode.gridPos.y + 1),
            cc.v2(curGridNode.gridPos.x - 1, curGridNode.gridPos.y),
            cc.v2(curGridNode.gridPos.x, curGridNode.gridPos.y - 1),
            cc.v2(curGridNode.gridPos.x + 1, curGridNode.gridPos.y + 1),
            cc.v2(curGridNode.gridPos.x - 1, curGridNode.gridPos.y + 1),
            cc.v2(curGridNode.gridPos.x - 1, curGridNode.gridPos.y - 1),
            cc.v2(curGridNode.gridPos.x + 1, curGridNode.gridPos.y - 1),
        ]
        gridPoss.forEach(gridPos => {
            let x = gridPos.x,
                y = gridPos.y
            if (x >= 0 && y >= 0 && x < this._widthNum && y < this._heightNum) {
                let gridNode = this._gridMap.get(x).get(y)
                if (gridNode !== curGridNode) {
                    if (gridNode.moveAbled && !gridNode.isClose && !gridNode.isOpen) {
                        this._openGridNodes.push(gridNode)
                        if (!gridNode.last) {
                            gridNode.last = curGridNode
                        }
                    }
                }
            }
        })
        if (this._openGridNodes.length > 0) {
            // let stepGridNodes = []
            for (let index = 0; index < this._openGridNodes.length; index++) {
                let gridNode = this._openGridNodes[index]
                if (gridNode !== endGridNode) {
                    if (!gridNode.isOpen) {
                        gridNode.isOpen = true
                        let curOffX = Math.abs(gridNode.gridPos.x - gridNode.last.gridPos.x),
                            curOffY = Math.abs(gridNode.gridPos.y - gridNode.last.gridPos.y),
                            expectOffX = Math.abs(endGridNode.gridPos.x - gridNode.gridPos.x),
                            expectOffY = Math.abs(endGridNode.gridPos.y - gridNode.gridPos.y)
                        gridNode.curStepNum = gridNode.last.curStepNum + curOffX + curOffY + (curOffX !== 0 && curOffY !== 0 && (- 0.5))
                        gridNode.expectStepNum = expectOffX + expectOffY + (expectOffX !== 0 && expectOffY !== 0 && (- 0.5))
                        let sumNum = gridNode.curStepNum + gridNode.expectStepNum
                        gridNode.sumNum = sumNum
                    }
                } else {
                    this._showResult(true, startGridNode, endGridNode)

                    return true
                }
            }
            if (this._getClosestOpenGridNodes(this._openGridNodes.sort((a, b) => a.sumNum - b.sumNum).shift(), startGridNode, endGridNode)) {
                return true
            }
        } else {
            this._showResult(false, startGridNode, endGridNode)

            return true
        }
        return false
    }

    /**
     * 处理搜索结果
     * @param success 是否找到路径
     * @param startGridNode 起点
     * @param endGridNode 终点
     */
    _showResult(success: boolean, startGridNode: GridNode, endGridNode: GridNode): void {
        // cc.log(`${cc.js.getClassName(this)} _showResult`)

        if (success) {
            this._steps = []
            this._findLast(endGridNode)
            // this._isSmart = false
            if (this._isSmart) {
                this._steps = this._optimizeResult(this._steps)
            }
            this._resultCall && this._resultCall(this._steps)
        } else {
            this._resultCall && this._resultCall(null)
        }
        this._resultCall = null
    }

    /**
     * 优化路径，使路径可以走斜线
     * @param steps 原始路径
     * @returns 优化后的路径
     */
    _optimizeResult(steps: GridNode[]): GridNode[] {
        // cc.log(`${cc.js.getClassName(this)} _optimizeResult`)

        let dealIndexes = []
        for (let index = 0; index < steps.length; index++) {
            let gridNode = steps[index]
            if (gridNode !== this._startGridNode && gridNode !== this._endGridNode) {
                let itemPos = cc.v2(gridNode.gridPos),
                    sc_last = gridNode.last,
                    lastPos = sc_last && sc_last.gridPos && cc.v2(sc_last.gridPos),
                    vector1 = lastPos && itemPos.sub(lastPos),
                    sc_next = gridNode.next,
                    nextPos = sc_next && sc_next.gridPos && cc.v2(sc_next.gridPos),
                    vector2 = nextPos && nextPos.sub(itemPos)
                if (vector1 && vector2) {
                    if (!cc.Vec2.strictEquals(vector1, vector2)) {
                        let vector3 = vector1.add(vector2),
                            x3 = vector3.x,
                            y3 = vector3.y,
                            unitX3 = vector3.div(Math.abs(x3)),
                            unitY3 = vector3.div(Math.abs(y3)),
                            allMoveAbled = true
                        for (let i = 0; i < Math.abs(x3); i++) {
                            let gridPos = lastPos.add(unitX3.scale(cc.v2(i + 0.5, i + 0.5))),
                                tempX1 = Math.ceil(gridPos.x),
                                tempX2 = Math.floor(gridPos.x),
                                tempY = Math.round(gridPos.y),
                                tempGridNode1 = this._gridMap.get(tempX1).get(tempY),
                                tempGridNode2 = this._gridMap.get(tempX2).get(tempY)
                            tempGridNode1.getComponent(tempGridNode1.name).nd_spSearch.active = true
                            tempGridNode2.getComponent(tempGridNode2.name).nd_spSearch.active = true
                            if (!tempGridNode1.moveAbled || !tempGridNode2.moveAbled) {
                                allMoveAbled = false
                            }
                        }
                        for (let j = 0; j < Math.abs(y3); j++) {
                            let gridPos = lastPos.add(unitY3.scale(cc.v2(j + 0.5, j + 0.5))),
                                tempY1 = Math.ceil(gridPos.y),
                                tempY2 = Math.floor(gridPos.y),
                                tempX = Math.round(gridPos.x),
                                tempGridNode1 = this._gridMap.get(tempX).get(tempY1),
                                tempGridNode2 = this._gridMap.get(tempX).get(tempY2)
                            tempGridNode1.getComponent(tempGridNode1.name).nd_spSearch.active = true
                            tempGridNode2.getComponent(tempGridNode2.name).nd_spSearch.active = true
                            if (!tempGridNode1.moveAbled || !tempGridNode2.moveAbled) {
                                allMoveAbled = false
                            }
                        }
                        if (allMoveAbled) {
                            dealIndexes.push(index)
                            break
                        }
                    }
                }
            }
        }
        let tempSteps = []
        dealIndexes.forEach(index => {
            steps[index] = null
        })
        steps.forEach(gridNode => {
            if (gridNode) {
                tempSteps.push(gridNode)
                gridNode.last = tempSteps[tempSteps.length - 2] || gridNode.last
                gridNode.last && (gridNode.last.next = gridNode)
            }
        })
        if (dealIndexes.length > 0) {
            return this._optimizeResult(tempSteps)
        } else {
            return steps
        }
    }

    /**
     * 倒序查找节点前后关系，填充路径
     * @param curGridNode 带查找的节点
     */
    _findLast(curGridNode: GridNode): void {
        // cc.log(`${cc.js.getClassName(this)} _findLast`)

        if (curGridNode) {
            this._steps.unshift(curGridNode)
            curGridNode.last && (curGridNode.last.next = curGridNode)
            this._findLast(curGridNode.last)
        }
    }

    //==============================================================================================================================
    //========================================================= 外部方法 ============================================================
    //==============================================================================================================================

    /**
     * 根据指定起点和终点寻路
     * @param startGridNode 起点
     * @param endGridNode 终点
     * @param call 回调(Array steps 路径)
     * @param isSmart 是否可以走斜线
     */
    searchWay(startGridNode: GridNode, endGridNode: GridNode, call: (steps: GridNode[]) => void, isSmart: boolean = true): void {
        cc.log(`${cc.js.getClassName(this)} searchWay`)

        this._gridMap.forEach((value, x) => {
            value.forEach((gridNode, y) => {
                this.resetGridNode(gridNode)
            })
        })
        this._openGridNodes = []
        this._closeItems = new Map()
        this._resultCall = call
        this._isSmart = isSmart

        this._startSearch(startGridNode, endGridNode)
    }

    /**
     * 初始化指定网格节点属性
     * @param gridNode 网格节点
     * @param gridPos 坐标
     */
    initGridNode(gridNode: GridNode, gridPos: GridPos): void {
        // cc.log(`${cc.js.getClassName(this)} initGridNode`)

        gridNode.gridPos = gridPos
        gridNode.moveAbled = true
        this.resetGridNode(gridNode)
    }

    /**
     * 重置网格节点的搜索状态
     * @param gridNode 网格节点
     */
    resetGridNode(gridNode: GridNode): void {
        // cc.log(`${cc.js.getClassName(this)} resetGridNode`)

        gridNode.isClose = false
        gridNode.isOpen = false
        gridNode.last = null
        gridNode.next = null
        gridNode.curStepNum = 0
    }

    /**
     * 设置网格节点是否可通行
     * @param gridNode 网格节点
     * @param bool 是否可通过
     */
    setMoveAbled(gridNode: GridNode, bool: boolean): void {
        // cc.log(`${cc.js.getClassName(this)} setMoveAbled`)

        gridNode.moveAbled = bool
    }
}